﻿using System;
using System.Collections.Generic;
using MinecraftEnchantCalculator.Abstractions;

namespace MinecraftEnchantCalculator.Core;

/// <summary>
///   铁砧树实现类，基于树形结构执行多个可附魔物品的合并操作
///   实现了IAnvil接口，通过构建平衡二叉树优化附魔合并的顺序和成本计算
/// </summary>
public class AnvilTree : IAnvil
{
  /// <summary>
  ///   对多个可附魔物品执行树形合并操作，通过平衡二叉树结构优化合并顺序
  /// </summary>
  /// <param name="enchantables">待合并的可附魔物品列表（至少需要2个物品）</param>
  /// <param name="operationCallback">
  ///   每次合并操作的回调函数，用于返回合并过程信息：
  ///   - 第一个参数：参与合并的左侧物品
  ///   - 第二个参数：参与合并的右侧物品
  ///   - 第三个参数：合并后生成的新物品
  /// </param>
  /// <exception cref="ArgumentException">当输入列表物品数量小于2时抛出</exception>
  public void Enchant(
    List<IEnchantable> enchantables, Action<IEnchantable, IEnchantable, IEnchantable> operationCallback
  )
  {
    var n = enchantables.Count;
    if (n < 2) throw new ArgumentException("Need at least two enchantables");

    var h = 0;
    while (1 << h < n) ++h;

    var leafs = new List<AnvilNode>();
    var root = BuildTree(leafs, h + 1, 0, ref n);

    leafs.Sort((x, y) => x.Weight.CompareTo(y.Weight));
    enchantables.Sort((x, y) => y.Value.CompareTo(x.Value));
    for (var i = 0; i < leafs.Count; i++) leafs[i].Enchantable = enchantables[i];

    EnchantNode(root!, operationCallback);
  }

  /// <summary>
  ///   递归构建平衡二叉树结构，用于规划物品合并的层级关系
  /// </summary>
  /// <param name="leafs">用于收集所有叶子节点的列表</param>
  /// <param name="height">当前树的目标高度</param>
  /// <param name="weight">节点权重，用于排序叶子节点</param>
  /// <param name="leafCount">剩余需要创建的叶子节点数量（引用传递）</param>
  /// <returns>构建完成的树节点，可能为null（当无需创建节点时）</returns>
  private static AnvilNode? BuildTree(
    List<AnvilNode> leafs, int height, int weight, ref int leafCount
  )
  {
    if (leafCount == 0 || height == 0)
      return null;

    var ans = new AnvilNode(weight) {
      Left = BuildTree(leafs, height - 1, weight, ref leafCount),
      Right = BuildTree(leafs, height - 1, weight + 1, ref leafCount)
    };

    if (ans.Left is null && ans.Right is null) {
      leafs.Add(ans);
      --leafCount;
      return ans;
    }

    return ans.Right is null ? ans.Left : ans;
  }

  /// <summary>
  ///   递归处理树节点的合并操作，从叶子节点开始向上逐层合并
  /// </summary>
  /// <param name="node">当前处理的树节点</param>
  /// <param name="operationCallback">合并操作的回调函数，用于传递合并结果</param>
  private static void EnchantNode(
    AnvilNode node, Action<IEnchantable, IEnchantable, IEnchantable> operationCallback
  )
  {
    AnvilNode? left = node.Left, right = node.Right;
    if (left is null || right is null)
      return;

    EnchantNode(left, operationCallback);
    EnchantNode(right, operationCallback);

    node.Enchantable = left.Enchantable.Merge(right.Enchantable);

    operationCallback(
      left.Enchantable, right.Enchantable, node.Enchantable
    );
  }

  /// <summary>
  ///   铁砧树的节点类，用于存储合并过程中的物品和层级关系
  /// </summary>
  private class AnvilNode
  {
    /// <summary>
    ///   初始化铁砧树节点
    /// </summary>
    /// <param name="weight">节点权重，用于排序叶子节点</param>
    public AnvilNode(int weight)
    {
      Weight = weight;
    }

    /// <summary>
    ///   当前节点存储的可附魔物品
    /// </summary>
    public IEnchantable Enchantable { get; set; } = null!;

    /// <summary>
    ///   节点权重，用于叶子节点的排序
    /// </summary>
    public int Weight { get; }

    /// <summary>
    ///   左子节点
    /// </summary>
    public AnvilNode? Left { get; init; }

    /// <summary>
    ///   右子节点
    /// </summary>
    public AnvilNode? Right { get; init; }
  }
}